package dp;

public class CoinChange322 {
    //TODO dp[amount]
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int a = 1; a <= amount; a++) {
            dp[a] = -1;
            for (int j = 0; j < coins.length; j++) {
                if (a >= coins[j] && dp[a-coins[j]] >= 0) {
                    int t = dp[a-coins[j]] + 1;
                    // 注意是取t最小的, 不是取最大的
                    if (dp[a] < 0 || t < dp[a]) {
                        dp[a] = t;
                    }
                }
            }
        }
        return dp[amount];
    }
}
